842C - Ilya And The Tree - CodeForces Solution

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define f(i, a, b)        for (int(i) = int(a); (i) < int(b); ++(i))
    // #define f(i,b)        for (int(i) = 0; (i) < int(b); ++(i))
    #define vi                  vector<int>
    #define vb                  vector<bool>
    #define ff first
    #define ss second
    #define pb push_back
    #define pf push_front
    #define ub upper_bound
    #define lb lower_bound
    #define prDouble(x) cout<<fixed<<setprecision(10)<<x
    #define pii                 pair<int, int>
    #define vpii                vector<pair<int, int> >

    #define w(x)                int x; cin >> x; while(x--)
    #define FIO                 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #define setbits(x) __builtin_popcountll(x)    //count number of setbits in a number
    #define max3(a, b, c)       max((a), max((b), (c)))
    #define min3(a, b, c)       min((a), min((b), (c)))
    #define mx_all(c)           *max_element((c).begin(), (c).end())
    #define mn_all(c)           *min_element((c).begin(), (c).end())
    #define all(x) x.begin(),x.end()
    #define siz(x) ((int)(x).size())
    #define yes cout<<"Yes"<<endl
    #define no cout<<"No"<<endl
    #define pb push_back
    #define vi vector<int>
    #define vb vector<bool>
    #define vs vector<string>
    #define vvi vector<vector<int>>
    #define pq priority_queue
    #define out(a) for(auto x9: a) cout<<x9<<" "; cout<<"\n";
    #define lld long double
    #define printall(a)         for (auto& (i) : (a)) cout << i << ' ';
    // int dp[100001];
    const ll MOD= 998244353,mod=1e9+7,N=200010,inf=1e12;
    const lld pi = 3.1415926535897932;
    ll accurateFloor(ll a, ll b) {
        ll val = a / b;
        while (val * b > a)
            val--;
        return val;
    }
    void yesno(bool xxx)
    {
        if(xxx)
        cout<<"Yes\n";
        else
        cout<<"No\n";
    }
    ll nCr(ll n, ll r)
    {
    if (n < r)
    return 0;
    if (r > n - r)
    r = n - r;
    ll ans = 1;
    ll i;
    for (i = 1; i <= r; i++)
    {
    ans *= n - r + i;
    ans /= i;
    }
    return ans;
    }
    ll binaryexp(ll a,ll b){
    ll ans=0;
    if(b<0)return 0;
    if(b==0)return 1;
    else if(b==1)return a;
    else if(b%2){
    ans=(a*(binaryexp((a*a)%mod,b/2)%mod))%mod;
    }
    else ans=binaryexp((a*a)%mod,b/2)%mod;
    return ans;
    }
    int gcd(int x,int y){
    if(y==0)return x;
    else return gcd(y,x%y);
    }

    long long gcd(long long int a, long long int b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
      
    // Function to return LCM of two numbers 
    long long lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }

    ll expo(ll a, ll b, ll m) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b = b >> 1;} return res%m ;}
    ll modinv(ll a , ll m ) {return expo(a , m-2 , m)%m;} // m is prime 


    vector<ll> arr(N),vis(N),g(N),ans(N),factors,cnt(N);
    vector<vector<ll>> adj(N);

    void dfs1(int node){
        vis[node]=1;
        for(auto child:adj[node]){
            if(vis[child]) continue;
            g[child]=__gcd(g[node],arr[child]);
            dfs1(child);
        }
    }

    void dfs2(int node,int depth){
        vis[node]=1;
        for(int i=0;i<factors.size();i++){
            cnt[i]+=((arr[node]%factors[i])==0);
            if(cnt[i]>=(depth-1)){
                ans[node]=max(ans[node],factors[i]);
            }
        }
        for(auto child:adj[node]){
            if(vis[child]) continue;
            dfs2(child,depth+1);
            for(int i=0;i<factors.size();i++){
                cnt[i]-=(arr[child]%factors[i]==0);
            }

        }
    }
int main(){
    ll n;
    cin>>n;
    for(int i=1;i<n+1;i++){
        cin>>arr[i];
    }
    for(int i=1;i*i<=arr[1];i++){
        if((arr[1]%i)==0){
            factors.pb(i);
            if((i*i)!=(arr[1]))
            factors.pb((arr[1])/i);
        }
    }
    // cout<<factors[3]<<endl;
    f(i,1,n){
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs1(1);
    sort(all(factors));
    f(i,1,n+1) vis[i]=0;
    dfs2(1,1);
    // cout<<g[3]<<endl;
    f(i,1,n+1){
        ans[i]=max(g[i],ans[i]);
        cout<<ans[i]<<" ";
    }
    cout<<endl;


    return 0;
}